package secondary

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
	请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

	例如:
	给定二叉树:[3,9,20,null,null,15,7],

		3
	   / \
	  9  20
		/  \
	   15   7
	返回其层次遍历结果：

	[
	  [3],
	  [20,9],
	  [15,7]
	]

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func levelOrder2(root *TreeNode) [][]int {
	if nil == root {
		return nil
	}
	queue := []*TreeNode{root}
	height := 1
	result := make([][]int, 0)
	for len(queue) != 0 {
		length := len(queue)
		res := make([]int, 0)
		for length != 0 {
			cur := queue[0]
			queue = queue[1:]
			if height%2 == 0 {
				res = append([]int{cur.Val}, res...)
			} else {
				res = append(res, cur.Val)
			}
			if nil != cur.Left {
				queue = append(queue, cur.Left)
			}
			if nil != cur.Right {
				queue = append(queue, cur.Right)
			}
			length--
		}
		height++
		result = append(result, res)
	}
	return result
}
